Ley de Gustafson

La ley de Gustafson (también conocida como ley de Gustafson-Barsis)^[1]es una ley en ciencia de la computación que establece que cualquier problema suficientemente grande puede ser eficientemente paralelizado.

La ley fue planteada por John L. Gustafson en su su artículo Reevaluating Amdahl's Law (En español: Reevaluando la ley de Amdahl), en 1988^[1]. En dicho artículo, Gustafson criticó el enfoque de la ley de Amdahl, en el cual se asume un problema con un tamaño fijo, y en el cual se concluye que el speedup obtenido al añadir paralelismo, está limitado por 1/s, donde s es la porción secuencial del programa. Gustafson plantea que ese resultado de la ley de Amdahl generó pesimismo sobre las posibilidades de la mejora de rendimiento con paralelismo, y que el error que tiene es que, en la práctica, al haber más procesadores, el tamaño del problema no se mantiene fijo, si no que aumenta, para aprovechar las capacidades del procesador. De esta manera, la mejora de rendimiento sí escala cuando se escala la cantidad de procesadores, en contraste con los resultados de la ley de Amdahl. ^[1]

El impacto de la ley de Gustafson fue el cambio de dirección de los objetivos de investigación hacia la selección o reformulación de problemas a fin de que fuera posible la solución de mayores problemas en el mismo intervalo de tiempo. En particular la ley redefine la eficiencia como una necesidad para minimizar la parte secuencial de un programa, incluso si esto incrementa la cantidad total de cálculos.

Definición

La ley de Gustafson se define así:

$S(P)=P-\alpha \cdot (P-1)$

donde S es el speedup, P es el número de procesadores, y $\alpha$ es la porción no paralelizable del proceso. Como se puede notar, la ley está expresada en términos de P.

Derivación de la ley

El tiempo de ejecución de un programa en una computadora paralela es descompuesto en:

$(a+b)$

donde $a$ es el tiempo secuencial y $b$ es el tiempo paralelo, en cualquiera de los P procesadores.

La suposición clave de Gustafson y Barsis es que la cantidad total de trabajo a realizar en paralelo varía linealmente con el número de procesadores. La implicación práctica es que un procesador capaz de procesar más de la carga de procesamiento asignada a este, puede ejecutar en paralelo otras tareas generalmente similares. Esto implica que b, el tiempo de procesamiento en paralelo por proceso, debe ser fijo mientras P varía. El tiempo correspondiente para el procesamiento secuencial es:

$a+P\cdot b.$

El speedup (aceleramiento) es, en concordancia:

$(a+P\cdot b)/(a+b).$

Definiendo

$\alpha =a/(a+b)$

como la fracción secuencial del tiempo de ejecución en paralelo, obtenemos

$S(P)=\alpha +P\cdot (1-\alpha )=P-\alpha \cdot (P-1).$

Por consiguiente, si $\alpha$ es pequeño, el aceleramiento es aproximadamente P, como es deseado. Incluso se puede dar el caso en que $\alpha$ disminuya mientras P junto con el tamaño del problema aumente; si esto se cumple, S se aproxima a P monótonamente con el crecimiento de P.

De esta forma, la Ley de Gustafson aparenta rescatar el procesamiento en paralelo de la Ley de Amdahl. Está basada en la idea de que si el tamaño de un problema puede crecer monotónicamente con P, entonces la fracción secuencial de la carga de trabajo no representará la parte dominante de dicha carga. Esto es posible haciendo la mayoría de las asignaciones de trabajo contenibles dentro del ámbito de procesamiento de un solo procesador; de aquí que un solo procesador pueda servir para múltiples asignaciones, mientras que una asignación no debe expandirse a más de un procesador. Esta es también la regla para proyectos en sitios de trabajo, teniendo muchos proyectos por sitio, pero solo un sitio por proyecto.

Metáfora de la conducción

La ley de Amdahl aproximadamente sugiere:

Supongamos que un auto está viajando entre dos ciudades que se encuentran a 60 millas de distancia, y ya ha estado una hora viajando la mitad de la distancia a 30 millas por hora. Sin importar cuán rápido viaje la mitad restante es imposible alcanzar una velocidad promedio de 90 millas por hora antes de terminar el recorrido. Debido a que ya le ha tomado 1 hora y ha de recorrer 60 millas; aunque viaje infinitamente rápido solo alcanzaría una velocidad promedio de 60 millas por hora.

La ley de Gustafson aproximadamente enuncia:

Supongamos que un auto ha estado viajando algún tiempo a 90 millas por hora. Teniendo distancia y tiempo suficiente para viajar, la velocidad promedio del auto podría alcanzar eventualmente las 90 millas por hora, sin importar cuánto o a qué velocidad haya viajado. Por ejemplo, si el auto demoró una hora viajando a 30 millas por hora, podría alcanzar las 90 millas por hora de velocidad promedio conduciendo a 120 millas por hora durante 2 horas, o a 150 millas por hora durante una hora, etc.

Aplicaciones

Aplicaciones en la investigación

La ley de Amdahl presupone que los requerimientos de cómputo se mantendrán invariables, dado el incremento del poder de procesamiento. En otras palabras, el análisis de la misma cantidad de datos toma menos tiempo dado más poder de cómputo. Gustafson, por otra parte, argumenta que más poder de cómputo causará que los datos sean analizados más profunda y cuidadosamente: pixel por pixel o unidad por unidad, en lugar de ser analizados a gran escala. Donde no sería posible o práctico simular el impacto de una detonación nuclear en todas las construcciones, autos y sus contenidos (incluyendo muebles, accesorios, etc.) debido a que tales cálculos tomarían más tiempo del disponible para dar una respuesta, el incremento del poder de cómputo incita a los investigadores a añadir más datos para simular más variables, brindado resultados más precisos.

Aplicaciones cotidianas en sistemas computacionales

La ley de Amdahl presenta una limitación en, por ejemplo, la capacidad de los núcleos múltiples de reducir el tiempo que toma a una computadora iniciar su sistema operativo y estar lista para el uso. Asumiendo que el proceso de iniciado fuera mayormente paralelizado, cuadruplicando el poder de cómputo en un sistema que toma un minuto para cargar, podría cargar en solo 15 segundos. Pero mayor paralelización fallaría eventualmente en hacer el inicio más rápido, si alguna parte del proceso de inicio fuera esencialmente secuencial. La ley de Gustafson argumenta que un aumento cuádruple del poder de cómputo conllevaría a un incremento similar en las capacidades del sistema. Si un minuto de tiempo de inicio de un sistema es aceptable para la mayoría de los usuarios, entonces esto es un punto de inicio desde donde incrementar las funcionalidades y características del sistema. El tiempo de inicio del sistema operativo se mantendrá igual, o sea un minuto, pero el nuevo sistema incluirá mejores características gráficas y funcionalidades para el usuario.

Limitaciones

Algunos problemas no tienen fundamentalmente grandes cantidades de datos. Por ejemplo, procesar un dato por ciudadano del mundo crece un bajo por ciento anualmente. El punto principal de la ley de Gustafson es que tales problemas no son los que más pueden explotar las ventajas del paralelismo.

Los algoritmos no lineales dificultan la utilización de las ventajas del paralelismo expuestas por la ley de Gustafson. Snyder^[2] muestra que un algoritmo O(N³) mediante la duplicación de la concurrencia solo permite el aumento de un 26% de la cantidad de datos. Por consiguiente, mientras sea posible ocupar grandemente la concurrencia, hacerlo puede traer una relativamente pequeña ventaja sobre la solución original; sin embargo en la práctica han ocurrido mejoras considerables.

Hill y Marty^[3] enfatizan además que métodos de acelerar la ejecución secuencial todavía son necesarios, incluso para máquinas con núcleos múltiples. Ellos señalan que métodos localmente ineficientes pueden ser globalmente eficientes cuando reducen la fase secuencial. Adicionalmente, Woo y Lee^[4] estudian la implicación de energía y poder en procesadores futuros de múltiples núcleos basados en la ley de Amdahl, mostrando que un procesador multinúcleo asimétrico puede alcanzar la mayor eficiencia energética posible mediante la activación del número óptimo de núcleos dado que la cantidad de paralelismo es conocida antes de la ejecución.

Véase también

Referencias

↑ ^a ^b ^c Reevaluating Amdahl's Law, John L. Gustafson, Communications of the ACM, volumen 31 (mayo 1988)
↑ Type Architectures, Shared Memory, and The Corrolary of Modest Potential, Lawrence Snyder, Ann. Rev. Comput. Sci. 1986. 1:289-317.
↑ Amdahl's Law in the Multicore Era, Mark D. Hill and Michael R. Marty, IEEE Computer, vol. 41, pp. 33–38, July 2008. Also UW CS-TR-2007-1593, April 2007.
↑ Extending Amdahl's Law for Energy-Efficient Computing in the Many-Core Era Archivado el 10 de octubre de 2012 en Wayback Machine., Dong Hyuk Woo and Hsien-Hsin S. Lee, IEEE Computer, vol. 41, No. 12, pp.24-31, December 2008.

Datos: Q1276790

[reevaluating-amdahl-1] Reevaluating Amdahl's Law, John L. Gustafson, Communications of the ACM, volumen 31 (mayo 1988)

[Snyder1986-2] Type Architectures, Shared Memory, and The Corrolary of Modest Potential, Lawrence Snyder, Ann. Rev. Comput. Sci. 1986. 1:289-317.

[Hill&Marty2008-3] Amdahl's Law in the Multicore Era, Mark D. Hill and Michael R. Marty, IEEE Computer, vol. 41, pp. 33–38, July 2008. Also UW CS-TR-2007-1593, April 2007.

[Woo&Lee2008-4] Extending Amdahl's Law for Energy-Efficient Computing in the Many-Core Era Archivado el 10 de octubre de 2012 en Wayback Machine., Dong Hyuk Woo and Hsien-Hsin S. Lee, IEEE Computer, vol. 41, No. 12, pp.24-31, December 2008.

[1]

[2]

[3]

[4]